package dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class wordBreak {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] mark = new boolean[s.length()];
        List<String> dict = new ArrayList<>();
        int start=0;
        for(String word: wordDict ){
            if (word.length()<=s.length()) {
                if (word.equals(s.substring(0, word.length()))) {
                    //初始化
                    mark[word.length()-1]=true;
                }
                dict.add(word);
            }
        }
        for(int i=0;i<s.length();i++){
            if (!mark[i]) {
                continue;
            }
            for(String word: dict){
                //无穷背包
                if (i+1+word.length()<=s.length()&&word.equals(s.substring(i+1,i+1+ word.length()))) {
                    mark[i+word.length()]=true;
                }
                if (mark[s.length()-1]) {
                    return true;
                }
            }
        }
        return mark[s.length()-1];
    }
    public static void main(String[] args) {
        wordBreak obj = new wordBreak();
        String s="catsandog";
        List<String> wordDict = new ArrayList<>(Arrays.asList("cats", "dog", "sand", "and", "cat"));
        // String s="applepenapple";
        // List<String> wordDict = new ArrayList<>(Arrays.asList("apple", "pen"));
        // String s="leetcode";
        // List<String> wordDict = new ArrayList<>(Arrays.asList("leet", "code"));
        System.out.println(obj.wordBreak(s, wordDict));
    }
}
